package Arrays;

import java.util.ArrayList;
import java.util.List;

public class _216_CombinationSumIII {
    List<List<Integer>> resultList = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        getSubComb(1,0,k,n,new ArrayList<Integer>());
        return resultList;
    }
    //in function,list is referenced,not copy
    public void getSubComb(int pos, int count, int N,int rest,List<Integer> tempList) {
        if (count == N-1) {
            for (int i = pos; i < 10; i++) {
                if (rest - i == 0) {
                    tempList.add(i);
                    resultList.add(tempList);
                    break;
                }
            }
        } else {
            for(int i=pos;i<10;i++) {
                if (rest - i > 0) {
                    List<Integer> list = new ArrayList<>();
                    list.addAll(tempList);
                    list.add(i);
                    getSubComb(i+1,count+1,N,rest-i,list);
                } else {
                    break;
                }
            }
        }
    }
}
